package com.example.stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
 * 假设压入栈的所有数字均不相等。
 *
 *  {1,2,3,4,5}为压栈序列，
 *  序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，
 *  但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列
 */
public class Leetcode_ToOffer31_ValidateStackSequences {
    public static void main(String[] args) {

    }

    /**
     * 思路:每次比较栈顶元素与弹出序列是否一致，一致则出栈
     *
     * 细节:
     *   建立一个辅助栈(用于保存压栈的顺序)
     *      循环向辅助栈中push压入序列的元素
     *      如果辅助栈中的栈顶元素与popped的当前元素不同，则继续将pushed中的元素压入辅助栈;
     *      如果它与当前弹出的元素相同，则继续弹出栈顶元素;
     *      循环后检查辅助栈是否为空。
     */
    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        // 用于保存压栈的顺序
        Deque<Integer> stack = new LinkedList<>();
        int i =0;
        for (int num : pushed) {
            stack.push(num);
            while (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}
